from typing import List, Optional


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        pre = None
        slow = fast = head
        # 一边反转前半部分，一边找中点
        while fast and fast.next:
            # fast指针更新两步
            fast = fast.next.next
            # 反转更新slow 指针
            next = slow.next
            slow.next = pre
            pre = slow
            slow = next
        # 处理奇数个节点的情况
        if fast:
            slow = slow.next
        # 从中点开始分别向前向后遍历，逐个比较是否相同
        while slow:
            if slow.val != pre.val:
                return False
            pre = pre.next
            slow = slow.next
        return True


if __name__ == '__main__':
    node1 = ListNode(1)
    node2 = ListNode(1)


    node1.next = node2
    # node2.next = node3

    solution = Solution()
    print(solution.isPalindrome(node1))
